//
// Created by 陈磊 on 16/8/26.
//

#ifndef MICROSOFTCODE_LINKEDLISTCODE_H
#define MICROSOFTCODE_LINKEDLISTCODE_H

struct LinkedNode{
    int value ;
    LinkedNode* next ;
};


class LinkedListCode {
    public:
        void reverseLinkedList(LinkedNode* head)  ;
        LinkedNode* makeRandomLinkedList(int size) ;
        void printLinkedList(LinkedNode* head) ;
        void mergeTwoSortedLinkedListToFirst(LinkedNode* pHeadOne,LinkedNode* pHeadTwo) ;
        void quickSort(LinkedNode* pHead,LinkedNode* pEnd) ;
        LinkedNode* getTailNode(LinkedNode* head) ;
        LinkedNode* findFirstPublicNode(LinkedNode* pHeadOne,LinkedNode* pHeadTwo) ;

        /*
         * 给定链表的头指针和一个结点指针，在 O(1)时间删除该结点。
         */
        void deleteNodeSubtle(LinkedNode* pHead ,LinkedNode* toBeDeleted) ;

        /*
         * 给定单链表，检测是否有环。
         */
        bool haveCircle(LinkedNode* pHead) ;

        void testMain() ;

    private:
        LinkedNode* _getPartition(LinkedNode* pHead,LinkedNode* pEnd) ;

};


#endif //MICROSOFTCODE_LINKEDLISTCODE_H
